#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
    int size;   // 塔块大小
    char start; // 起始塔
    char end;   // 目标塔
    char sup;   // 辅助塔
} Move;

void stack_hanoi(int n, char start, char sup, char end) //用栈解决汉诺塔问题
{
    Move *moveStack = (Move *)malloc(n * sizeof(Move));
    int top = -1;

    Move move;
    move.size = n;
    move.start = start;
    move.end = end;
    move.sup = sup;

    moveStack[++top] = move;

    while (top >= 0)
    {
        Move currentMove = moveStack[top--];

        if (currentMove.size == 1)
        {
            printf("从%c移动一个盘子到%c\n", currentMove.start, currentMove.end);
        }
        else
        {
            Move move1, move2, move3;

            move1.size = currentMove.size - 1;
            move1.start = currentMove.start;
            move1.end = currentMove.sup;
            move1.sup = currentMove.end;

            move2.size = 1;
            move2.start = currentMove.start;
            move2.end = currentMove.end;
            move2.sup = currentMove.sup;

            move3.size = currentMove.size - 1;
            move3.start = currentMove.sup;
            move3.end = currentMove.end;
            move3.sup = currentMove.start;

            moveStack[++top] = move3;
            moveStack[++top] = move2;
            moveStack[++top] = move1;
        }
    }

    free(moveStack);
}

void recursion_hanoi(int num, char A, char B, char C) //递归解法
{
    if (num == 1)
        printf("将第%d个盘从%c移动到%c\n", num, A, C);
    else
    {
        recursion_hanoi(num - 1, A, C, B);
        printf("将第%d个盘从%c移动到%c\n", num, A, C);
        recursion_hanoi(num - 1, B, A, C);
    }
}

int main()
{
    int num = 3; //盘子个数为3
    char A = 'A', B = 'B', C = 'C';
    // recursion_hanoi(num, A, B, C); //递归
    stack_hanoi(num, A, B, C);
    return 0;
}